本篇同步發布於Blog:[解題] LeetCode - 189 Rotate Array

平台：

LeetCode

題號：

189 - Rotate Array

題目連結：

https://leetcode.com/problems/rotate-array/

題目說明：

        輸入1個陣列nums和位移量k，求nums元素往右k旋轉後的結果。題目要求只能用O(1)的空間複雜度。

比如範例輸入的nums = [1,2,3,4,5,6,7], k = 3，每個元素都往右移3個位置變成[5,6,7,1,2,3,4]。

解題方法：

   　如果用暴力法，變成要執行O(n * k)的執行時間。

更有效率的解，只需要O(n)的執行時間，一開始從index = 0，不斷往後k位移做換值的動作，直到執行次數等於nums的長度。特別的是陣列長度和k都是偶數時，不斷k位移又會回到同樣的index，因此需判斷k又回到原點時，需換下一個index。

再加速的方法是判斷k是否為0或者k是n的倍數，可以不用運算。再者k超過的n的長度時，可以把k = k % n。

難度為Easy

程式碼 (C++ 與 C#)：

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if((k % n)== 0){
            return;
        }
        
        k = k % n;
        int temp1, temp2;
        int counts = 0;
        for(int start = 0 ; counts < n;++start){
            int current = start;
            temp1 = nums[start];
            do{
                int next = (current + k) % n;
                temp2 = nums[next];
                nums[next] = temp1;
                temp1 = temp2;
                current = next;
                counts++;
            }while(current!= start);
        }
    }
};

int main() {
	Solution sol;
	vector<int> nums{1,2,3,4,5,6,7};
	sol.rotate(nums, 3);
	for(int i = 0 ; i < nums.size();++i){
		cout << " " << nums[i];
	}
	return 0;
}

using System;

namespace LeetCode189
{
	public class Solution {
	    public void Rotate(int[] nums, int k) {
	        int n = nums.Length;
	        if((k % n)== 0){
	            return;
	        }
	        
	        k = k % n;
	        int temp1, temp2;
	        int counts = 0;
	        for(int start = 0 ; counts < n;++start){
	            int current = start;
	            temp1 = nums[start];
	            do{
	                int next = (current + k) % n;
	                temp2 = nums[next];
	                nums[next] = temp1;
	                temp1 = temp2;
	                current = next;
	                counts++;
	            }while(current!= start);
	        }
	    }
	}
	public class Program
	{
		public static void Main()
		{
			int[] nums = new int[]{1,2,3,4,5,6,7};
			Solution sol = new Solution();
			sol.Rotate(nums, 3);
			for(int i = 0;i < nums.Length;++i){
				Console.Write(" " + nums[i]);
			}
		}
	}
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/100-199/189.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/100-199/189.cs